package dome3;

/**
 * Created with IntelliJ IDEA.
 * Description: 双向链表
 * User: 王圆豪
 * Date: 2024-07-22
 * Time: 18:48
 */
public class DlinkedList implements IList{
    ListNode head;
    ListNode last;
    static class ListNode{
        int val;
        ListNode pre;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    @Override
    public void addFirst(int data) {
        if (head == null) {
            head = last = new ListNode(data);
            return;
        }
        ListNode cur = new ListNode(data);
        cur.next = head;
        head.pre = cur;
        head = cur;
    }

    @Override
    public void addLast(int data) {
        if (head == null) {
            head = last = new ListNode(data);
            return;
        }
        ListNode cur = new ListNode(data);
        last.next = cur;
        cur.pre = last;
        last = cur;
    }

    @Override
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("位置不合理！！！");
            return;
        }
        ListNode tmp = new ListNode(data);
        ListNode cur = head;
        int pos = 0;
        while (cur.next != null) {
            if (pos == index) {
                break;
            }
            pos++;
            cur = cur.next;
        }
        cur.pre.next = tmp;
        tmp.pre = cur.pre;
        cur.pre = tmp;
        tmp.next = cur;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                //开始删除
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.pre = null;
                    }
                }else {
                    cur.pre.next = cur.next;
                    if(cur.next == null) {
                        last = last.pre;
                    }else {
                        cur.next.pre = cur.pre;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

    @Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                //开始删除
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.pre = null;
                    }
                }else {
                    cur.pre.next = cur.next;
                    if(cur.next == null) {
                        last = last.pre;
                    }else {
                        cur.next.pre = cur.pre;
                    }
                }
            }
            cur = cur.next;
        }
    }

    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void clear() {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        while (cur.next != last) {
            cur.next.next.pre = cur;
            cur.next = cur.next.next;
        }
        head = null;
        last = null;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}
